from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        # 遍历数组，固定第一个元素
        for i in range(n - 2):
            # 取出当前固定的元素
            x = nums[i]
            # 如果当前元素和前一个元素相同，跳过当前循环，避免重复的三元组
            if i > 0 and x == nums[i - 1]:
                continue
            # 初始化第二个指针，从当前元素的下一个位置开始
            j = i + 1
            # 初始化第三个指针，从数组的末尾开始
            k = n - 1
            # 当第二个指针小于第三个指针时，继续循环
            while j < k:
                # 计算三个指针所指元素的和
                s = x + nums[j] + nums[k]
                # 如果和大于 0，说明第三个指针所指元素过大，将第三个指针向左移动
                if s > 0:
                    k -= 1
                # 如果和小于 0，说明第二个指针所指元素过小，将第二个指针向右移动
                elif s < 0:
                    j += 1
                else:
                    # 如果和等于 0，说明找到了一个满足条件的三元组
                    ans.append([x, nums[j], nums[k]])
                    # 移动第二个指针，并跳过重复元素，避免重复的三元组
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    # 移动第三个指针，并跳过重复元素，避免重复的三元组
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
        # 返回所有满足条件的三元组
        return ans
